package geometry;

/**
 * closest pair in two different groups
 * 
 * @author yinzichen
 */
public class ClosestPair {

	static long a[][], b[][], buf[][];

	static double eps = 1e-7;

	static double closet(int l, int r) {
		double dist = Double.MAX_VALUE;
		if (r == l + 1) {
			if (a[l][2] != a[r][2])
				dist = distance(a[l], a[r]);
			if (a[l][1] > a[r][1]) {
				b[l] = a[r];
				b[r] = a[l];
			} else {
				b[l] = a[l];
				b[r] = a[r];
			}
		} else if (r != l) {
			int m = (l + r) >> 1;
			dist = Math.min(closet(l, m), closet(m + 1, r));
			merge(l, m, r);
			int s = 0;
			int i;
			for (i = l; i <= m; i++)
				if (Math.abs(b[i][0] - a[m][0]) + eps < dist)
					buf[s++] = b[i];
			int mm = s - 1;
			for (; i <= r; i++)
				if (Math.abs(b[i][0] - a[m][0]) + eps < dist)
					buf[s++] = b[i];
			for (i = l; i <= mm; i++) {
				int j = mm + 1;
				while (j <= s) {
					if (buf[i][2] != buf[j][2]) {
						dist = Math.min(distance(buf[i], buf[j]), dist);
					}
					if (buf[j][1] - buf[i][1] + eps > dist)
						break;
					j++;
				}
			}
		}
		return dist;
	}

	// merge sort by y-axis values
	static void merge(int l, int m, int r) {
		int i = l, j = m + 1, k = l;
		while (i < m + 1 && j < r + 1) {
			if (b[i][1] < b[j][1]) {
				buf[k] = b[i++];
			} else {
				buf[k] = b[j++];
			}
			k++;
		}
		for (; i < m + 1; i++, k++) {
			buf[k] = b[i];
		}
		for (; j < r + 1; j++, k++) {
			buf[k] = b[j];
		}
		for (i = l; i < k; i++) {
			b[i] = buf[i];
		}
	}

	static double distance(long a[], long b[]) {
		return Math.sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1])
				* (a[1] - b[1]));
	}

}